package arr;

/**
 * create by yongli on 2020-07-21 23:28
 * 567812
 */

public class FindElement {
    public static void main(String[] args) {

        int[] a = {13, 16, 18, 30, 1, 3, 4};
        int n = 16;
        int n2 = 15;
        int n3 = 1;
        int idx = findInOrderedResvere(n3, a);
        System.out.println(idx);

    }

    // 在有序数组旋转后查找元素
    public static int findInOrderedResvere(int n, int[] a) {
        int reverseIdx = BifindReverse(0, a.length - 1, a);
        if (a[reverseIdx] == n) {
            return reverseIdx;
        }
        if (n < a[reverseIdx] && n > a[reverseIdx - 1]) {
            return -1;
        }
        if (n < a[0]) {
            int idx = Bifind(n, reverseIdx + 1, a.length - 1, a);
            return idx;

        } else {
            int idx = Bifind(n, 0, reverseIdx - 1, a);
            return idx;

        }

    }

    // 采用二分法方式在有序数组中查找,使用递归
    private static int Bifind(int n, int start, int end, int[] arr) {
        if (start > end) {
            return -1;
        }
        if (start == end) {
            if (arr[start] == n) {
                return start;
            } else {
                // 为找到
                return -1;
            }
        }
        int mid = (start + end) / 2;
        int m = arr[mid];
        if (m == n) {
            return mid;
        } else if (m < arr[mid]) {
            return Bifind(n, start, mid - 1, arr);
        } else {
            return Bifind(n, mid + 1, end, arr);
        }

    }

    // 采用二分法查找旋转点,前提条件旋转点比存在
    private static int BifindReverse(int start, int end, int[] arr) {
        int mid = (start + end) / 2;
        // 最小
        if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
            return mid + 1;
        } else if (arr[mid] <= arr[mid + 1]) {
            return BifindReverse(mid, end, arr);
        } else return BifindReverse(start, mid, arr);
    }
}
